//这道题比较复杂，不做要求，比赛时暴力求解，对暴力代码尽量优化，减少不必要得计算，能尽量得部分分数即可

#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef long long ll;
typedef unsigned long long LL;
const int N = 100005;
int k, cnt = 0, dis[N], head[N];
struct edge {
    int dis, to, nxt;
} e[N<<4];
struct node {
    int u, d;
    node(int x, int y) : u(x), d(y) { }
    inline bool operator < (const node & a) const {
        return d > a.d;
    }
} ;
inline void add(int u, int v, int w) {
    e[++ cnt].dis = w; e[cnt].to = v; e[cnt].nxt = head[u]; head[u] = cnt;
}
inline void Dijkstra(int s) {
    memset(dis, 0x3f, sizeof(dis));
    dis[s] = 0;
    priority_queue<node> q;
    q.push(node(s, 0));
    while (!q.empty()) {
        node h = q.top(); q.pop();
        int u = h.u, d = h.d;
        if (d != dis[u]) continue;
        for (register int i=head[u]; i; i=e[i].nxt) {
            int to = e[i].to;
            if (dis[u] + e[i].dis < dis[to]) {
                dis[to] = dis[u] + e[i].dis;
                q.push(node(to, dis[to]));
            }
        }
    }
    return;
}
signed main() {
    scanf("%d",&k);
    for (register int i=0; i<k; ++i)
        for (register int j=0; j<10; ++j) {
            add(i, (i*10+j)%k, j);
        }
    for (register int i=1; i<10; ++i)
        add(k, i%k, i);
    Dijkstra(k);
    cout << dis[0];
    return 0;
}